import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/19 10:22
 * @description BFS, 寻找的是最少操作数，每次操作都清晰，BFS中谁先到达目标数，那么操作次数就最少
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int minimumOperations(int[] nums, int start, int goal) {
        // BFS中入栈的元素，参与下一次寻找
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(start);
        // 二元组（s, cnt) 统计到达值s的步数cnt
        Map<Integer, Integer> map = new HashMap<>();
        map.put(start, 0);

        while (!deque.isEmpty()) {
            int cur = deque.pollFirst();
            int step = map.get(cur);
            // 获取值后，进行bfs
            for(int i : nums) {
                // 三种运算结果
                int[] result = {cur + i, cur - i, cur ^ i};
                for (int next : result) {
                    if (next == goal) {
                        return step + 1;
                    }
                    // 如果超出范围，那么跳出，这个next不参与BFS
                    if (next < 0 || next > 1000) {
                        continue;
                    }
                    // 如果包含了这个数，说明已经以更少的次数到达过，丢弃
                    if (map.containsKey(next)) {
                        continue;
                    }
                    map.put(next, step + 1);
                    deque.addLast(next);
                }
            }
        }
        return -1;
    }
}
